//===----------------------------------------------------------------------===//
//
//                         CMU-DB Project (15-445/645)
//                         ***DO NO SHARE PUBLICLY***
//
// Identification: src/page/b_plus_tree_leaf_page.cpp
//
// Copyright (c) 2018, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <sstream>

#include "common/exception.h"
#include "common/rid.h"
#include "storage/page/b_plus_tree_leaf_page.h"

namespace bustub {

/*****************************************************************************
 * HELPER METHODS AND UTILITIES
 *****************************************************************************/

/**
 * Init method after creating a new leaf page
 * Including set page type, set current size to zero, set next page id and set max size
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Init(int max_size) {
  SetPageType(IndexPageType::LEAF_PAGE);
  SetSize(0);
  SetMaxSize(max_size);
  SetMinSize(max_size / 2);
  next_page_id_ = INVALID_PAGE_ID;
}

/**
 * Helper methods to set/get next page id
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetNextPageId() const -> page_id_t { return next_page_id_; }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SetNextPageId(page_id_t next_page_id) { next_page_id_ = next_page_id; }

/*
 * Helper method to find and return the key associated with input "index"(a.k.a
 * array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::KeyAt(int index) const -> KeyType { return array_[index].first; }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SetKeyAt(int index, const KeyType &key) {
  // BUSTUB_ASSERT(index > 0, "index lt 0");
  array_[index].first = key;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &cmp) -> bool {
  // 叶子结点从0下标开始
  // array_[GetSize()] = MappingType(key, value);
  int size = GetSize();
  bool found = false;
  for (int i = size - 1; i >= 0; i--) {
    if (cmp(key, array_[i].first) < 0) {
      array_[i + 1] = array_[i];
    } else {
      array_[i + 1] = MappingType(key, value);
      found = true;
      break;
    }
  }
  if (!found) {
    array_[0] = MappingType(key, value);
  }
  IncreaseSize(1);
  return true;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Remove(const KeyType &key, const KeyComparator &cmp) -> bool {
  int size = GetSize();
  bool found = false;
  for (int i = 0; i < size; i++) {
    if (cmp(key, array_[i].first) == 0) {
      found = true;
      for (int j = i; j < size - 1; j++) {
        array_[j] = array_[j + 1];
      }
      break;
    }
  }
  if (found) {
    IncreaseSize(-1);
  }
  return found;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetArray() -> MappingType * { return array_; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetArray() const -> const MappingType * { return array_; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::ValueAt(int index) const -> ValueType { return array_[index].second; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::LowerBound(const KeyType &key, const KeyComparator &cmp) -> int {
  int left = 0;
  int right = GetSize();
  while (left < right) {
    int mid = left + (right - left) / 2;  // 第一个大于等于T,查找，插入
    if (cmp(key, array_[mid].first) <= 0) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::UpperBound(const KeyType &key, const KeyComparator &cmp) -> int {
  int left = 0;
  int right = GetSize();
  while (left < right) {
    int mid = left + (right - left) / 2;  // 第一个大于等于T,查找，插入
    if (cmp(key, array_[mid].first) >= 0) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left - 1;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetValue(const KeyType &key, std::vector<ValueType> *result, const KeyComparator &cmp,
                                          int &index) const -> bool {
  int size = GetSize();
  for (int i = 0; i < size; i++) {
    if (cmp(key, array_[i].first) == 0) {
      result->push_back(array_[i].second);
      index = i;
      return true;
    }
  }
  return false;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::CopyArray(const MappingType *array, int start, int size, int dst_start) -> void {
  for (int i = 0; i < size; i++) {
    array_[i + dst_start] = array[start + i];
  }
  SetSize(size + dst_start);
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Remove(int index) -> MappingType {
  auto ret = array_[index];
  int size = GetSize();
  for (int j = index; j < size - 1; j++) {
    array_[j] = array_[j + 1];
  }
  IncreaseSize(-1);
  return ret;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(int index, const MappingType &kv) -> void {
  IncreaseSize(1);
  int size = GetSize();
  for (int j = size - 1; j > index; j--) {
    array_[j] = array_[j - 1];
  }
  array_[index] = kv;
}

template class BPlusTreeLeafPage<GenericKey<4>, RID, GenericComparator<4>>;
template class BPlusTreeLeafPage<GenericKey<8>, RID, GenericComparator<8>>;
template class BPlusTreeLeafPage<GenericKey<16>, RID, GenericComparator<16>>;
template class BPlusTreeLeafPage<GenericKey<32>, RID, GenericComparator<32>>;
template class BPlusTreeLeafPage<GenericKey<64>, RID, GenericComparator<64>>;
}  // namespace bustub
